package cn.mayday.algorithms.year2021.month1.E堆和TopN专题;

import java.util.PriorityQueue;

/**
 * 输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：arr = [3,2,1], k = 2
 * 输出：[1,2] 或者 [2,1]
 * <p>
 * 示例 2：
 * <p>
 * 输入：arr = [0,1,2,1], k = 1
 * 输出：[0]
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author Mayday05
 * @date 2021/1/10 15:52
 */
public class Leetcode040MinKNumbers {

    public static void main(String[] args) {
        int[] test1 = {3, 2, 1};
        int[] result1 = new Leetcode040MinKNumbers().getLeastNumbers(test1, 2);

        System.out.println("result1 = " + result1);
    }


    // 方法一： 最小的K个数-大顶堆
    // 时间复杂度O(NLogK)【因此理论上要循环N次，而堆每次旋转时间复杂度为LogK】，空间复杂度O(K) 【因为大根堆最多K个数】
    public int[] getLeastNumbers1(int[] arr, int k) {
        int[] result = new int[k];
        if (k == 0) {
            return result;
        }

        // 定义大顶堆，Java中优先级队列即为小顶堆,因此需要取反比较规则
        PriorityQueue<Integer> maxQueue = new PriorityQueue<>((o1, o2) -> o2 - o1);

        // 初始化堆
        for (int i = 0; i < k; i++) {
            maxQueue.offer(arr[i]);
        }

        for (int i = k; i < arr.length; i++) {
            int top = maxQueue.peek();
            if (arr[i] < top) {
                maxQueue.poll(); // 出堆
                maxQueue.offer(arr[i]);// 入堆
            }
        }

        for (int i = 0; i < k; i++) {
            result[i] = maxQueue.poll();
        }

        return result;
    }

    // 方法二：快排或者冒泡，不需要全部完成，完成K个即可
    // 时间复杂度，空间复杂度

    public int[] getLeastNumbers(int[] arr, int k) {
        int[] result = new int[k];
        if (k == 0) {
            return result;
        }

        // 冒牌，只需要K个即可
        for (int i = 0; i < k; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] > arr[j]) {
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }

        for (int i = 0; i < k;i++) {
            result[i] = arr[i];
        }
        return result;
    }


    // 方法三 快排思想
    // 思路和算法
    //
    // 可以借鉴快速排序的思想。我们知道快排的划分函数每次执行完后都能将数组分成两个部分，
    // 小于等于分界值 pivot 的元素的都会被放到数组的左边，大于的都会被放到数组的右边，然后返回分界值的下标。
    // 与快速排序不同的是，快速排序会根据分界值的下标递归处理划分的两侧，而这里我们只处理划分的一边。



    // 方法三：二叉搜索树
    // 时间复杂度，空间复杂度

}
